1. Field of the Invention
The present invention relates to cryptography systems and methods, and particularly to a system and method for securing scalar multiplication against differential power attacks.
2. Description of the Related Art
Elliptic Curve Cryptosystems (ECC), originally proposed by Niel Koblitz and Victor Miller in 1985, offer a serious alternative to earlier public key cryptosystems, such as Rivest-Shamir-Adleman (RSA) and ElGamal, with much shorter key size. To date, no significant breakthroughs have been made in determining weaknesses in the ECC algorithm, which is based on the discrete logarithm problem over points on an elliptic curve. The fact that the problem appears so difficult to crack means that key sizes can be reduced considerably, even exponentially. This has caused ECC to become a serious challenger to RSA and ElGamal cryptosystems. Because of these advantages, ECC have been recently incorporated in many standards. ECC have gained popularity for cryptographic applications because of the short key, and are considered to be particularly suitable for implementation on smart cards or mobile devices.
An elliptic curve over a finite field GF(q) defines a set of points (x,y) that satisfy the elliptic curve equation together with the point O, known as the “point at infinity”. The “point at infinity” does not satisfy the elliptic curve equation. The coordinates x and y of the elliptic curve points are elements of the field GF(q), where q=pm and p is prime.
Equations (1) and (2) define the elliptic curve equations for the fields GF(p) and GF(2m), respectively:y2=x3+ax+b  (1)where a, bεGF(p) and 4a+27b2≠0(mod p); andy2+xy=x3+ax2+b  (2)where a, bεGF(2m) and b≠0.
The set of discrete points on an elliptic curve form an abelian group (commutative group), whose group operation is known as point addition. Bounds for the number of discrete points n on an elliptic curve over a finite field GF(q) are defined by Hasse's theorem, given in Equation (3), where the symbol n represents the number of points on the elliptic curve and where q=pm represents the number of elements in the underlying finite field:q+1−2√{square root over (q)}≦n≦q+1+2√{square root over (q)}.  (3)
Elliptic curve “point addition” is defined according to the “chord-tangent process”. Point addition over GF(p) is described as follows: Let P and Q be two distinct points on an elliptic curve E defined over the real numbers with Q≠−P (Q is not the additive inverse of P). The addition of P and Q is the point R=P+Q, where R is the additive inverse of S, and S is a third point on the elliptic curve intercepted by the straight line through points P and Q. For the curve under consideration, R is the reflection of the point S with respect to the x-axis, that is, if R is the point (x,y), then S is the point (x,−y).
When P=Q and P≠−P, the addition of P and Q is the point R, where R=2P and R is the additive inverse of S, and S is the third point on the elliptic curve intercepted by the straight line tangent to the curve at point P. This operation is referred to as “point doubling”.
The “point at infinity”, O, is the additive identity of the group. The most relevant operations involving O are the following: the addition of a point P and O is equal to P (i.e., P+O=P); and the addition of a point P and its additive inverse, −P, is equal to O (i.e., P−P=O). If P is a point on the curve, then −P is also a point on the curve.
The point operation used by elliptic curve cryptosystems is referred to as point multiplication. This operation is also referred to as scalar point multiplication. The point multiplication operation is denoted as kP, where k is an integer number and P is point on the elliptic curve. The operation kP represents the addition of k copies of point P, as shown in Equation (4) below:
                    kP        =                                                            P                +                P                +                …                +                P                            ︸                                      k              ⁢                                                          ⁢              times              ⁢                                                          ⁢              P                                .                                    (        4        )            
Elliptic curve cryptosystems are built over cyclic groups. Each group contains a finite number of points, n, that can be represented as scalar multiples of a generator point: iP for i=0, 1, . . . , n−1, where P is a generator of the group. The order of point P is n, which implies that nP=O and iP≠−O for 1<i<n−1. The order of each point on the group must divide n. Consequently, a point multiplication kQ for k>n can be computed as (k mod n)Q.
Scalar multiplication is the basic operation for ECC. Scalar multiplication in the group of points of an elliptic curve is the analogue of exponentiation in the multiplicative group of integers modulo a fixed integer m. Computing kP can be performed using a straightforward double-and-add approach based on the binary representation of k=kl-1, . . . , k0 where kl-1 is the most significant bit of k. Other scalar multiplication methods have been proposed in the literature.
One of the simplest scalar multiplication algorithms is the double-and-add point multiplication algorithm, which is the so-called binary algorithm. Algorithm 1 shows a typical double-and-add scalar multiplication algorithm. The algorithm inspects the multiplier k. For each inspected bit, the algorithm performs a point double, and if the inspected bit is one, the algorithm also performs a point add:
Algorithm 1: Double-and-AddInputs: P,kOutput: kPInitialization: Q[0] = 0; Q[1] = PScalar Multiplication: for i = 0 to m − 1  if ki = 1 then Q[0] = ADD(Q[0],Q[1]  Q[1] = DBL(Q[1]) end forreturn Q[0]
In the above algorithm, the “DBL” operation is a simple point doubling operation; e.g., Q[1]=DBL(Q[1]) simply means updating Q[1] as Q[1]=2Q[1]. Similarly, the “ADD” operation is a simple point adding operation; e.g., Q[0]=ADD(Q[0],Q[1]) simply means updating Q[0] as Q[0]=Q[0]+Q[1]. As noted above, kP can be computed using a straightforward binary method based on the binary expression of multiplier k. A conventional prior art scalar multiplication method for elliptic cryptosystems is shown in the U.S. Patent Application Publication US 2009/0214023 A1, which is hereby incorporated by reference in its entirety.
The binary scalar multiplication method shown in Algorithm 1 is the most straightforward scalar multiplication method. It inspects the bits of the scalar multiplier k, and if the inspected bit ki=0, only point doubling is performed. If, however, the inspected bit ki=1, both point doubling and point addition are performed. The binary method requires in point doublings and an average of m/2 point additions.
Power analysis attacks are usually divided into two types: Simple Power Analysis (SPA) attacks and Differential Power Analysis (DPA) attacks. SPA attacks consist of observing the power consumption during a single execution of a cryptographic algorithm. The power consumption analysis may also enable one to distinguish between point addition and point doubling. Differential Power Analysis (DPA) attack combines the SPA attack with an error-correcting technique using statistical analysis. More importantly, classical DPA attacks have been extensively researched for each cryptosystem, and new types of DPA attacks are continuously being developed. Many of the existing countermeasures are vulnerable to the more recent attacks, including the “Doubling Attack”, the Refined Power Analysis (RPA) and the Zero-Value Point Analysis (ZVP).
DPA attacks use error-correction techniques and statistical analysis to extract small differences in the power consumption signals. Several countermeasures have been proposed to provide security against DPA attacks, such as utilizing algorithms based on randomizing the private exponent, blinding the base point P, randomizing the projective coordinates, using a random isomorphism of an elliptic curve, and using special forms of certain elliptic curves. All of these countermeasures, however, add computational overhead and are still vulnerable to the more recent DPA attacks, e.g. the Doubling Attack, the Refined Power Analysis (RPA) and the Zero-Value Point (ZVP) attack. It would be desirable to provide an efficient countermeasure against DPA attacks which requires no additional computational overhead.
Thus, a system and method for securing scalar multiplication against differential power attacks solving the aforementioned problems is desired.